
//2115.从给定原材料找到所有可以做出的菜
class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        //依旧是拓扑排序,只不过将数字更改为了字符串,但是原理不变
        unordered_map<string ,int> need_dish;   //记录每一个菜需要的原料个数
        unordered_map<string ,vector<string>> dish_made;  //记录每个原料可以做什么菜

        int n=recipes.size();
        for(int i=0;i<n;i++)     //记录每一个原料可以做那些菜,并记录每一个菜需要多少原料
        {
            string& rp=recipes[i];
            auto& nums=ingredients[i];
            need_dish[rp]=nums.size();
            for(auto& str:nums)
                dish_made[str].push_back(rp);
        }

        queue<string> q;
        for(auto& sp:supplies)
            if(need_dish.count(sp)==0) q.push(sp);   //将不需要其他制作的原料入队列


        vector<string> ret;
        while(!q.empty())
        {
            int sz=q.size();
            for(int i=0;i<sz;i++)
            {
                auto dish=q.front();
                q.pop();
                auto& nums=dish_made[dish];   //nums存储该dish可以做那些菜
                for(auto& str:nums)
                {
                    if(--need_dish[str]==0)   //将可以制作的菜原料-1,如果所有原料都有了,就可以进行制作了
                    {
                        ret.push_back(str);
                        q.push(str);
                    }
                }                    
            }
        }
        return ret;
    }
};